package com.leetcode.题库.score1;

import java.util.*;

public class Main {
    static List<Integer> findStartEndNodes(int[][] edges) {
        Map<Integer, List<Integer>> graph = new HashMap<>();
        Map<Integer, Integer> inDegree = new HashMap<>();
        Map<Integer, Integer> outDegree = new HashMap<>();
        Set<Integer> nodes = new HashSet<>();

        // Build graph and compute degrees
        for (int[] edge : edges) {
            int u = edge[0], v = edge[1];
            graph.putIfAbsent(u, new ArrayList<>());
            graph.get(u).add(v);
            inDegree.put(v, inDegree.getOrDefault(v, 0) + 1);
            outDegree.put(u, outDegree.getOrDefault(u, 0) + 1);
            nodes.add(u);
            nodes.add(v);
        }

        // Detect cycle
        Set<Integer> visited = new HashSet<>();
        Set<Integer> recStack = new HashSet<>();
        for (Integer node : nodes) {
            if (!visited.contains(node) && isCyclic(node, graph, visited, recStack)) {
                return Arrays.asList(-1);
            }
        }

        List<Integer> startNodes = new ArrayList<>();
        List<Integer> endNodes = new ArrayList<>();
        for (Integer node : nodes) {
            if (!inDegree.containsKey(node)) {
                startNodes.add(node);
            }
            if (!outDegree.containsKey(node)) {
                endNodes.add(node);
            }
        }
        Collections.sort(endNodes, Collections.reverseOrder());

        startNodes.addAll(endNodes);
        return startNodes;
    }

    static boolean isCyclic(Integer node, Map<Integer, List<Integer>> graph, Set<Integer> visited, Set<Integer> recStack) {
        if (recStack.contains(node)) {
            return true;
        }
        if (visited.add(node)) {
            recStack.add(node);
            List<Integer> neighbors = graph.getOrDefault(node, Collections.emptyList());
            for (Integer neighbor : neighbors) {
                if (isCyclic(neighbor, graph, visited, recStack)) {
                    return true;
                }
            }
            recStack.remove(node);
        }
        return false;
    }

    public static void main(String[] args) {
        int[][] edges = {{0, 1}, {0, 2}, {1, 2}, {2, 3}};
        System.out.println(findStartEndNodes(edges));
    }
}


